package thired.class18_Mirrors;

public class Class01_MirrisTraversal {
    public static class Node {
        public int value;
        Node left;
        Node right;

        public Node(int data) {
            this.value = data;
        }
    }

    public static void process(Node root) {
        if (root == null) {
            return;
        }
        // 1
        process(root.left);
        // 2
        process(root.right);
        // 3
    }
    public static void mirrors(Node head){
        if (head == null) {
            return;
        }
        Node cur = head;
        Node mostRight = null;
        while (cur != null) {
            mostRight = cur.left;
            if (mostRight != null){
                while (mostRight.right != null && mostRight.right != cur){
                    mostRight = mostRight.right;
                }
                if(mostRight.right == null){
                    mostRight.right = cur;
                    cur = cur.left;
                    continue;
                }else{
                    mostRight.right = null;
                }
            }
            cur = cur.right;
        }
    }

    public static void morrisPre(Node head) {
        if(head != null);
        Node cur = head;
        Node mostRight = null;
        while (cur != null){
            mostRight = cur.left;
            if(mostRight != null){
                while (mostRight.right != null && mostRight.right != cur){
                    mostRight = mostRight.right;
                }
                if(mostRight.right == null){
                    System.out.print(cur.value + " ");
                    mostRight.right = cur;
                    cur = cur.left;
                    continue;
                }else{
                    mostRight.right = null;
                }
            }else{
                System.out.print(cur.value + " ");
            }
            cur = cur.right;
        }
        System.out.println(" ");
    }

    public static void morrisIn(Node head){
        if(head != null);
        Node cur = head;
        Node mostRight = null;
        while (cur != null){
            mostRight = cur.left;
            if(mostRight != null){
                while (mostRight.right != null && mostRight.right != cur){
                    mostRight = mostRight.right;
                }
                if(mostRight.right == null){
                    mostRight.right = cur;
                    cur = cur.left;
                    continue;
                }else{
                    System.out.print(cur.value + " ");
                    mostRight.right = null;
                }
            }else{
                System.out.print(cur.value + " ");
            }
            cur = cur.right;
        }
        System.out.println(" ");
    }

    public static void morrisPos(Node head){
        if(head != null);
        Node cur = head;
        Node mostRight = null;
        while (cur != null){
            mostRight = cur.left;
            if(mostRight != null){
                while (mostRight.right != null && mostRight.right != cur){
                    mostRight = mostRight.right;
                }
                if(mostRight.right == null){
                    mostRight.right = cur;
                    cur = cur.left;
                    continue;
                }else{
                    mostRight.right = null;
                    printReverse(cur.left);
                }
            }
            cur = cur.right;
        }
        printReverse(head);
        System.out.println(" ");
    }
    public static void printReverse(Node head){
        if(head == null) return;
        Node tail = reverse(head);
        //todo print
        Node cur = tail;
        while (cur != null) {
            System.out.print(cur.value + " ");
            cur = cur.right;
        }
        reverse(tail);
    }
    public static Node reverse(Node head){
     Node pre = null;
     Node cur = head;
     Node next = null;
     while (cur != null){
         next = cur.right;
         cur.right = pre;
         pre = cur;
         cur = next;
     }
     return pre;
    }

    public static void main(String[] args) {
        Node head = new Node(4);
        head.left = new Node(2);
        head.right = new Node(6);
        head.left.left = new Node(1);
        head.left.right = new Node(3);
        head.right.left = new Node(5);
        head.right.right = new Node(7);
//        printTree(head);
        morrisIn(head);
        morrisPre(head);
        morrisPos(head);
//        printTree(head);
        System.out.println("===================");

    }

}
